﻿using System;
using System.Collections.Generic;
using System.Text;
using System.Diagnostics;

namespace QuickSort
{
    class Program
    {
        public static void Main(string[] args)
        {

            int[] arr = { 4, 3, 2, 1, -1, 99, 12, 33, 99, 10 };
            q_sort(ref arr);
            foreach (int i in arr)
            {
                Console.WriteLine(i);
            }
        }

        public static void q_sort(ref int[] input)
        {
            System.Collections.Stack stack = new System.Collections.Stack();
            int pivot;
            int pivotIndex = 0;
            int leftIndex = pivotIndex + 1;
            int rightIndex = input.Length - 1;

            stack.Push(pivotIndex);//Push always with left and right
            stack.Push(rightIndex);

            int leftIndexOfSubSet, rightIndexOfSubset;

            while (stack.Count > 0)
            {
                rightIndexOfSubset = (int)stack.Pop();//pop always with right and left
                leftIndexOfSubSet = (int)stack.Pop();

                leftIndex = leftIndexOfSubSet + 1;
                pivotIndex = leftIndexOfSubSet;
                rightIndex = rightIndexOfSubset;

                pivot = input[pivotIndex];

                if (leftIndex > rightIndex)
                    continue;

                while (leftIndex < rightIndex)
                {
                    while ((leftIndex <= rightIndex) && (input[leftIndex] <= pivot))
                        leftIndex++;	//increment right to find the greater 
                    //element than the pivot

                    while ((leftIndex <= rightIndex) && (input[rightIndex] >= pivot))
                        rightIndex--;//decrement right to find the 
                    //smaller element than the pivot

                    if (rightIndex >= leftIndex)   //if right index is 
                        //greater then only swap
                        SwapElement(ref input, leftIndex, rightIndex);
                }

                if (pivotIndex <= rightIndex)
                    if (input[pivotIndex] > input[rightIndex])
                        SwapElement(ref input, pivotIndex, rightIndex);

                if (leftIndexOfSubSet < rightIndex)
                {
                    stack.Push(leftIndexOfSubSet);
                    stack.Push(rightIndex - 1);
                }

                if (rightIndexOfSubset > rightIndex)
                {
                    stack.Push(rightIndex + 1);
                    stack.Push(rightIndexOfSubset);
                }
            }
        }

        private static void SwapElement(ref int[] arr, int left, int right)
        {
            int temp = arr[left];
            arr[left] = arr[right];
            arr[right] = temp;
        }

        /// Sort the array between a low and high bound in either ascending or descending order
        /// Parameters: 
        ///      int  nFirst : between 0 and the upper bound of the array.
        ///      int  nLast  : between 0 and the upper bound of the array.
        ///                  : must be guaranteed >= nFirst.
        ///      bool bAscend: true  - sort in ascending order
        ///                  : false - sort in descending order
        //private bool ExecuteActualSort(int nFirst, int nLast, bool bAscend)
        //{
        //    bool bSortOK = false;

        //    try
        //    {
        //        int i, j, nStkPtr = 0, nTmp;
        //        bool bSortCompleted = false, bDirection = true;

        //        // get the maximum size of stack required:
        //        int nStackMax = (int)((Math.Log(nLast) + 3) * 2); // from Knuth Vol 3.
        //        // Note, +3 is added because: 
        //        // +1 to round up rather than down, 
        //        // +1 because it's a full bottom-up stack (ie Stack[0] is never used),
        //        // +1 because data array is zero-indexed.

        //        int[,] nStack = new int[nStackMax, 2];

        //        do
        //        {
        //            do
        //            {
        //                i = nFirst;
        //                j = nLast;
        //                bDirection = true;

        //                do
        //                {
        //                    if ((nData[i] > nData[j]) == bAscend)
        //                    {
        //                        // Swap the two items in the list pointed to by i and j
        //                        nTmp = nData[i];
        //                        nData[i] = nData[j];
        //                        nData[j] = nTmp;
        //                        bDirection = !bDirection;
        //                    }

        //                    if (bDirection)
        //                        j--;
        //                    else
        //                        i++;

        //                }
        //                while (i < j);

        //                if (i + 1 < nLast)
        //                {
        //                    // There's another partition to be sorted
        //                    nStkPtr++;
        //                    nStack[nStkPtr, 0] = i + 1;
        //                    nStack[nStkPtr, 1] = nLast;
        //                }
        //                nLast = i - 1;

        //            }
        //            while (nFirst < nLast);

        //            if (nStkPtr == 0)
        //            {
        //                // No more partitions to sort, so by definition we've finished!
        //                bSortCompleted = true;
        //            }

        //            else
        //            {
        //                // Pop the most recently stored partition and sort that
        //                nFirst = nStack[nStkPtr, 0];
        //                nLast = nStack[nStkPtr, 1];
        //                nStkPtr--;
        //            }
        //        }

        //        while (!bSortCompleted);

        //        bSortOK = true;
        //    }

        //    catch { }

        //    return bSortOK;
        //}
    }



    
}